package formal.hash;

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * @author DengYuan2
 * @create 2021-01-31 21:12
 */
public class H_128 {
    public static void main(String[] args) {
        int[] nums = {100,4,200,1,3,2};
//        int[] nums = {1,1,1,1};
//        int[] nums = {9,1,4,7,3,-1,0,5,8,-1,6};
//        int[] nums = {0,3,7,2,5,8,4,6,0,1};
        int res = longestConsecutive2(nums);
        System.out.println(res);
    }

    /**
     * 我的写法-排序后处理，可以完成，但不是O(n)的复杂度啊
     * @param nums
     * @return
     */
    public static int longestConsecutive(int[] nums) {
        if (nums.length==0){
            return 0;
        }
        Arrays.sort(nums);
        int len=1;
        int max = 1;
        for (int i = 0; i < nums.length-1; ) {
            if (nums[i]==nums[i+1]){
                i++;
                continue;
            }
            if (nums[i]+1==nums[++i]){
                len++;
                max=Math.max(max,len);
            }else {
                len=1;
            }
        }
        return max;
    }

    /**
     * 大神的写法
     * @param nums
     * @return
     */
    public static int longestConsecutive2(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>(nums.length);
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i],1);
        }
        for (int i:map.keySet()){
            forward(map,i);
        }

        return maxCount(map);
    }

    public static int forward(Map<Integer,Integer> map,int value){
        if (!map.containsKey(value)){
            return 0;
        }
        int cnt=1+forward(map,value+1);
        map.put(value,cnt);
        return cnt;
    }

    public static int maxCount(Map<Integer,Integer> map){
        int max = 0;
        for (int i:map.keySet()){
            max=Math.max(max,map.get(i));
        }
        return max;
    }

    /**
     * 官方-使用hashset，检查时只检查每个连续集的第一个数
     * @param nums
     * @return
     */
    public static int longestConsecutive3(int[] nums){
        HashSet<Integer> set = new HashSet<>();
        int longest = 1;
        int length=1;
        for (int num:nums){
            set.add(num);
        }
        for (int num:set){
            length=1;
            //todo 巧妙地省掉了重复的检查！！
            if (!set.contains(num-1)){
                int cur=num;
                while (set.contains(cur+1)){
                    length++;
                    cur=cur+1;
                }
                longest=Math.max(longest,length);
            }
        }
        return longest;
    }
}
